# include <stdio.h>
# include <stdlib.h>
# include <string.h>

# define true 1
# define false 0

typedef int bool;

int **matrix(int size);
int MSTree(int **matrix, int size);

int main() {
	// create matrix
	int size;
	printf("size : ");
	scanf("%d", &size);
	int **map = matrix(size);

	int count = MSTree(map, size);
	printf("count : %d\n", count);
	return 0;
}

// 矩阵
int **matrix(int size) {
	// create matrix
	int ** matrix = (int **) malloc(sizeof(int*)*size);
	for (int i = 0; i < size; i++)
		matrix[i] = (int *) malloc(sizeof(int) * size);

	for (int i = 0; i < size; i++)
		for (int j = 0; j < size; j++)
			scanf("%d", &matrix[i][j]);

	return matrix;
}

int MSTree(int **matrix, int size) {
	// 标志数组
	bool searched[size];
	for (int i = 0; i < size; i++)
		searched[i] = false;
	searched[0] = true;
	// 边集
	int edge[size];
	for (int i = 0; i < size; i++)
		edge[i] = matrix[0][i];
	// 循环
	int i, j, min, last, count = 0;
	for (i = 1; i < size; i++) {
		min = 0;
		// 从 edge 中找最小代价边连通。last保留了连通的顶点
		for (j = 0; j < size; j++) {
			if (searched[j] == false && edge[j] != 0 && (min == 0 || edge[j] < min)) {
				min = edge[j];
				last = j;
			}
		}
		searched[last] = true;
		count += min;
		printf("%d\t", min);
		// 用新添加的顶点的连通边的权值，更新 edge
		// 保证 edge 中的边是最小代价边
		for (j = 0; j < size; j++) {
			// 因为我们输入的，没有边标记权为0，所以有一个或判断
			// 如果是第一次边，就添加权；否则，判断最小代价边
			if (searched[j] == false && matrix[last][j] != 0 && (edge[j] == 0 || matrix[last][j] < edge[j])) {
				edge[j] = matrix[last][j];
			}
		}
	}
	printf("\n");
	return count;
}
